Automaten

Automaten im Alltag

  • Snackautomat
  • Getränkeautomat
  • Fahrstuhl
  • Waschmaschine
  • Computer

Sonstiger Nutzen von Automaten

  • Sprachen erkennen
    • Syntax überprüfen
    • Programmcode in Maschinencode übersetzen
  • Programme strukturieren (Modellierung)
  • Beweise führen

Automaten in der Informatik

Unter anderem gibt es…

  • Turingmaschinen
  • Linear beschränkte Automaten
  • Kellerautomaten
  • Endliche Automaten
    • Deterministische Automaten
    • Nichtdeterministische Automaten
    • Akzeptoren
    • Transduktoren
      • Moore-Automaten
      • Mealy-Automaten
  • \omega-Automaten

Mealy-Automaten

Ein Mealy-Automat kann als 7-Tupel
A=(Q,\Sigma , \Omega , \delta, \lambda, q_0, F) definiert werden:

  • Q ist eine endliche Menge von Zuständen
  • \Sigma ist das Eingabealphabet
  • \Omega ist das Ausgabealphabet
  • \delta ist die Übergangsfunktion \delta : Q\times \Sigma \rightarrow Q
  • \lambda ist die Ausgabefunktion \lambda : Q\rightarrow \Omega
  • q_0\in Q
  • F\subseteq Q
F kann weggelassen werden, wenn keine Sprache untersucht werden soll

Beispiel Mealy-Automaten

Arbeitsauftrag:

  1. Gehe auf https://bit.ly/2uMIBUo und bearbeite auf den vier Unterseiten (System 1-4) die Aufgaben.
  2. Versuche anschließend jeweils das Verhalten durch die folgende Tabelle zu beschreiben.
gedrückter Schalter Türkonstellation
1
2
3

// reveal.js plugins